// 有n件物品和1个最多能背重量w的背包，第i件物品的重量是`weight[i]`,得到的价值为`value[i]`,
// 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大
// 思路1，动态规划，二维dp
// 1. 确定dp数组，`dp[i][j]`,表示从0-i的物品里任意取，放进容量为j的背包，价值总和最大是多少
// 2. 确定递推公式，`dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`
// 3. dp数组初始化
//     1. 当j为0， `dp[i][0] = 0`
//     2. 当i为0，当`j < weight[0]` `dp[0][j] = 0`,容量太小放不进去
//     3. 当i为0，当`j >= weight[0]` `dp[0][j] = value[0]`,容量可以放进去0的物品
// 4. 遍历顺序

function fun(inputArr) {
    let [M, N] = inputArr[0]
    let weight = inputArr[1]
    let value = inputArr[2]
    let dp = new Array(M).fill(0).map(_ => new Array(N+1).fill(0))
    // 初始化dp[0][j]，当只有一个物品
    for (let j = weight[0]; j <= N; j++) {
        dp[0][j] = value[0]
    }
    for (let i = 1; i < M; i++) {
        for (let j = 0; j <= N; j++) {
            if (j < weight[i]) {
                // i的重量太大，背包太小，放不进去, 结果和不放当前物品一样
                dp[i][j] = dp[i-1][j]
            } else {
                // j的容量足够，两种情况，i物品可以放，或者不放，取两者中大的那个
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
            }
        }        
    }
    return dp[M-1][N]
}

let inputArr = [
    [3, 4],
    [1, 3, 4],
    [15, 20, 30],
]

console.log(fun(inputArr))

// 思路2，动态规划，一维dp数组，滚动数组
// 1. dp数组的含义，容量为j的背包，所背物品的最大价值
// 2. 确定递推公式，`dp[j] = Math.max(dp[j], dp[j - weight[i]]) + value[i]`
// 3. dp初始化 `dp[0] = 0`
// 4. 遍历顺序，必须是从后往前，对于二维dp，`dp[i][j]`是根据`dp[i-1][j]`计算而来，一维dp，倒序遍历是为了保证左边的值依旧是上一层的状态，不会重复计算，必须先遍历物品后遍历背包，因为如果先遍历背包，每个背包只能放一个物品
// 5. 举例

function fun(inputArr) {
    let [M, N] = inputArr[0]
    let weight = inputArr[1]
    let value = inputArr[2]
    let dp = new Array(N + 1).fill(0)
    // 这儿必须先遍历物品，因为01背包每个物品只能用一次
    for (let i = 0; i < M; i++) {
        // 这儿得倒着遍历，因为正着会导致重复计算
        for (let j = N; j >= weight[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
        }        
    }
    return dp[N]
}
console.log(fun(inputArr))